#pragma once

#include <AVUIArray.h>

namespace AVUI {

template<class T>
struct ItemStructMap
{
private:
    struct Entry
    {
        int Key;
        T Value;
    };

public:
    ItemStructMap() : Count(0) {}

    int EnsureEntry(int key)
    {
        int length = Search(key);
        if (length < 0)
        {
            if (Entries == NULL)
            {
                Entries = array_allocate<Entry>(4);
            }
            length = ~length;
            TArrayPtr<Entry> pEntries = Entries;
            if (Count + 1 > Entries->get_Length())
            {
                pEntries = array_allocate<Entry>(Entries->get_Length() * 2);
                Copy(Entries, 0, pEntries, 0, length);
            }
            Copy(Entries, length, pEntries, length + 1, Count - length);
            Entries = pEntries;
            Entries[length] = Entry();
            Entries[length].Key = key;
            Count++;
        }
        return length;
    }

    int Search(int key)
    {
        int num = 0x7fffffff;
        int index = 0;
        if (Count > 4)
        {
            int num3 = 0;
            int num4 = Count - 1;
            while (num3 <= num4)
            {
                index = (num4 + num3) / 2;
                num = Entries[index].Key;
                if (key == num)
                {
                    return index;
                }
                if (key < num)
                {
                    num4 = index - 1;
                }
                else
                {
                    num3 = index + 1;
                }
            }
        }
        else
        {
            for (int i = 0; i < Count; i++)
            {
                index = i;
                num = Entries[index].Key;
                if (key == num)
                {
                    return index;
                }
                if (key < num)
                {
                    break;
                }
            }
        }
        if (key > num)
        {
            index++;
        }
        return ~index;
    }

    void RemoveAt(int removeIndex)
    {
        for(int idx = removeIndex; idx < Count - 1; idx++)
        {
            Entries[idx] = Entries[idx + 1];
        }
        Entries[Count - 1] = Entry();
        Count--;
    }

    int Count;
    TArrayPtr<Entry> Entries;

private:

    static void Copy(TArrayPtr<Entry> rgArrayFrom, int startIndexFrom, TArrayPtr<Entry> rgArrayTo, int startIndexTo, int count)
    {
        for(int idx = count - 1; idx >= 0; idx--)
        {
            rgArrayTo[startIndexTo + idx] = rgArrayFrom[startIndexFrom + idx];
        }
    }
};

};
